import networkx as nx

def is_path_valid(network_topology, path):
    """检查路径是否在拓扑图中有效"""
    return all(network_topology.has_edge(path[i], path[i+1]) for i in range(len(path)-1))

def classify_traffic_paths(new_demand_matrix, old_optimal_paths, new_optimal_paths):
    """分类通信对，区分需要重构和不需要重构的路径"""
    recon_pairs, no_recon_pairs, link_usage = [], [], {}
    for pair, new_path in new_optimal_paths.items():
        if pair[0]==pair[1]:
            continue
        else:
            old_path = old_optimal_paths.get(pair, [])
        if new_path != old_path:
            recon_pairs.append(pair)
        else:
            no_recon_pairs.append(pair)
            # for i in range(len(new_path) - 1):
            #     link = (new_path[i], new_path[i + 1])
            #     link_usage[link] = link_usage.get(link, 0) + new_demand_matrix[pair]
    # return recon_pairs, no_recon_pairs, link_usage
    return recon_pairs, no_recon_pairs

def compute_max_delay(network_topology, no_recon_pairs, new_optimal_paths, new_demand_matrix):
    """计算不需要重构通信对的最大时延"""
    max_delay = 0
    for pair in no_recon_pairs:
        path = new_optimal_paths[pair]
        max_path_delay = max(
            new_demand_matrix[pair] / network_topology[path[i]][path[i+1]]['capacity']
            for i in range(len(path) - 1)
        )
        max_delay = max(max_delay, max_path_delay)
    return max_delay

def update_link_capacities(network_topology, link_usage):
    """减少不需要重构通信对占用的带宽容量"""
    for link, usage in link_usage.items():
        network_topology[link[0]][link[1]]['capacity'] -= usage

def find_min_max_delay_path(network_topology, src, dst, demand):
    """寻找最优路径（最小化最大时延）"""
    try:
        paths = list(nx.all_shortest_paths(network_topology, source=src, target=dst))
        best_path, min_max_delay = None, float('inf')
        for path in paths:
            max_delay = max(
                demand / network_topology[path[i]][path[i+1]]['capacity']
                for i in range(len(path) - 1)
            )
            if max_delay < min_max_delay:
                best_path, min_max_delay = path, max_delay
        return best_path, min_max_delay
    except nx.NetworkXNoPath:
        return None, float('inf')

def dynamic_traffic_reconfiguration(new_demand_matrix, network_topology, old_optimal_paths, new_optimal_paths):
    """主函数：执行动态流量重构优化"""
    recon_pairs, no_recon_pairs, link_usage = classify_traffic_paths(new_demand_matrix, old_optimal_paths, new_optimal_paths)
    max_no_recon_delay = compute_max_delay(network_topology, no_recon_pairs, new_optimal_paths, new_demand_matrix)
    update_link_capacities(network_topology, link_usage)
    reconfigured_paths, delays = {}, {}
    for pair in sorted(recon_pairs, key=lambda x: new_demand_matrix[x], reverse=True):
        best_path, max_delay = find_min_max_delay_path(network_topology, pair[0], pair[1], new_demand_matrix[pair])
        reconfigured_paths[pair] = best_path
        delays[pair] = max_delay
    return reconfigured_paths, max_no_recon_delay, delays
